1. Field of the Invention
The present invention relates to combination multiplication and addition operations in a computing environment. More particularly, the present invention relates to an apparatus for performing nonparallel and parallel multiplication/addition operations, and a method for operating that apparatus.
2. The Background Art
In modern computers, it is often true that multiplication operations must be performed in order to satisfy a given objective. Those multiplication operations are often performed in either of two ways, traditional and parallel.
This disclosure primarily concerns itself with traditional multiplication where two numbers such as those seen in FIG. 1A are split into upper and lower halves such as those seen in FIG. 1B. The upper and lower halves are then multiplied together in four operations, i.e the upper half of the first number is multiplied with the upper and lower halves of the second number, and the lower half of the first number is multiplied with the upper and lower halves of the second number, and then the four results are added together to form the final result of the multiplication.
Therefore, two numbers xe2x80x9cAxe2x80x9d and xe2x80x9cBxe2x80x9d (shown here as numbers 10 and 12, each being 32-bits wide in this example) being multiplied together will each be broken into 16-bit halves, resulting in an upper half 14 and a lower half 16 from original number 10, and an upper half and a lower half 20 from original number 12.
Once the numbers are split apart into halves, and operation known as booth decoding is performed on one of the two halves as a first step in the multiplication of that number with the other number.
Booth decoding is a process by which overlapping groups of three bits each chosen from a first number are used to determine quantities of the second number which must be added together in order to produce a correct final multiplication result. In the example which follows, a first number and a second number are to be multiplied together. The second number is used as the key in booth decoding. In booth decoding when using the lower bits of the second number, a leading zero is added as the least significant bit of the lower half of the second number resulting in three-bit groups such as booth groups 22, 24, 26, 28, 30, 34, 36, and 38. Group 38 has two zeros added as most significant bits of the lower half, in order to properly complete that group.
When determining booth groups corresponding to the upper half of the second number, prior art systems again add a zero as the least significant bit of that upper half and use that zero when determining the rightmost booth group such as booth group 40. The remaining booth groups such as booth groups 42, 44, 46, 48, 50, 52, and 54 are then determined as previously described.
In, order to determine the nine booth groups associated with this lower half of the second number, and also properly use those nine booth groups, the prior art uses the apparatus depicted in FIG. 2.
Referring to FIG. 2, prior art system 56 includes booth recoder 58 which has and input for receiving a first number and an input for receiving a second number. Booth recoder 58 has nine outputs, each of those nine outputs providing partial products corresponding to the respective booth groups 22, 24, 26, 28, 30, 32, 34,.36, and 38. Eight of the nine outputs are provided in groups of four to two 4:2 compressors 60 and 62 the outputs of which are said to a third 4:2 compressor 64.
The ninth output 66 of booth recoder 58 together with the two outputs 68 and 70 of 4:2 compressor 64 are provided to 3:2 compressor 72. The two outputs of 3:2 compressor 72 are then provided to adder 74 to perform the final addition operation required. Output 76 of adder 74 is the final result of the multiplication.
While prior art systems are suitable for their intended purpose they require hardware which is unnecessary and which requires valuable space which could otherwise be used for different purpose. It would therefore be beneficial to provide a system which requires less hardware and therefore requires less space. This benefit and others are provided by the present invention.
The present invention provides an apparatus for booth decoding which stores the most significant bit of the lower half of the number used as the key for booth decoding. By using this stored bit to determine the rightmost booth group corresponding to the upper half of the key, booth decoding may be accomplished more quickly using an apparatus that is simpler and smaller than prior art assemblies.